#include <stdio.h>
#include <stdlib.h>

//插入排序
/*
每次将一个待排序的记录按其关键字大小插入到前已经排好的子序列中，直到全部记录插入完成

时间复杂度 O(n²)

*/
void InsertSort(int A[], int n)
{
    int i, j, temp;
    for (i = 1; i < n; i++)
    {
        if (A[i] < A[i - 1])
        {
            temp = A[i];
            for (j = i - 1; j >= 0 && A[j] > temp; --j)
            {
                A[j + 1] = A[j];
            }
            A[j + 1] = temp;
        }
    }
}

//优化
/*
折半插入排序

在选择元素要插入的位置时，采用折半查找寻找插入位置

*/

int main()
{
    printf("\n\n========================================================================\n\n");

    printf("\n\n========================================================================\n\n");
    return 0;
}